In computer graphics the shape of a displayed object can be approximated by a set of geometric primitives such as polygons or curvilinear elements such as polynomials, splines, or NURBS (Non-Uniform Rational B-Splines. These geometric primitives can be described in terms their position in a predetermined set of spatial coordinates using two or three-dimensional coordinates of their vertices or end points and additional data may also be used such as derivatives or normals.
A rigid body is one in which the vertices used to describe the object do not undergo a displacement relative to a body centered coordinate system, where the origin of the body centered coordinate system may be the center of mass of the object. In contrast, a deformable object is one in which the vertices used to describe the object undergo deformation relative to the body centered coordinate system.
In a dynamic animation of an object the new coordinate positions of a rigid body can be found in terms of translations and rotations of the object. These calculations can be directly calculated using matrix multiplication in which a rotation-translation matrix is multiplied by a vertices-data matrix that stores the coordinate positions of the vertices of the object. However, a dynamic animation of a deformable object involves not only the translation and rotation of the vertices of the object, but also the relative displacement of each the vertices with respect to the body centered coordinate system. The relative displacement is difficult to calculate and therefore, it would require the specification of each of the vertices for each image in the animation. Storing the data necessary to define each of the vertices in space for each image in the animation could require a very large amount of storage area. In some instances, the animation that includes a deformable object may be transmitted in real time over a data network, such as the internet, as streamed video. In this instance the amount of data to stream over the network includes the coordinates of the vertices defining an object in each frame. Data streaming this data would require a very high bandwidth connection to allow the large amount of data to be transmitted at a data rate sufficient to establish the proper images.
Therefore what is needed in the art is an apparatus and method to allow the data corresponding to the vertices of a deformable object to be efficiently stored or transmitted.
A method and apparatus are disclosed for analyzing a three-dimensional (3D) object and reducing the amount of data necessary to accurately reproduce the image. In particular, an 3D object is analyzed and a set of vertices is selected and formed into a vertices-data matrix A. This matrix A is analyzed using a singular value decomposition (SVD) technique that forms the matrices U, W, and V, wherein A=UWVT. In addition, the singular values in the matrix W associated with the vertices-data-matrix A are determined. These singular values can be truncated or filtered and the dimensions of the vertices-data-matrix A can be reduced thereby. In a data streaming application having a source and a destination, a constant product of VWT is formed and provided to the destination. The source then forms row vectors Ui of the matrix U, from the row vectors of the reduced dimension matrix A, according to Ui=AiVWxe2x88x921. The destination receives row vectors of U and reconstructs the 3D object according to A=UWVT.